Educational_Codeforces_Round_81(Rated_for_Div. 2)_D题

题目大意

求$gcd(a, m) = gcd(a+x, m), 0 <= x < m, 1 <= a < m <= 10^{10}$的$x$的个数

题解

已知$a < m, 0 <= x < m$，根据最大公约数的性质$a >= b, gcd(a, b)=gcd(a-b,b)$，所以如果$a+x>=m$那么$gcd(a+x,m)=gcd(a+x-m,m)$即$a+x$可以写成$(a+x)\%m$，令$x’=(a+x)\%m,0 <= x’ < m$，则有$(x’,m)=(a,m)$，设$(a,m)=d$那么$(x’,m)=d$，那么$(x’/d, m/d)=1$由于$0 <= x’ < m$，那么$0 <= x’/d < m/d$，答案就是求$φ(m/d)$

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
#define dbg(x) cout << #x"=" << x << endl;
int T;
LL a,m;

void solve(){
    cin >> a >> m;
    LL n = m/__gcd(a, m);
    LL ans = n;
    for(int i = 2; i <= n/i; ++i){
        if(n%i == 0){
            ans = ans / i * (i - 1);
            while(n % i == 0) n /= i;
        }
    }
    if(n > 1) ans = ans / n * (n - 1);
    cout << ans << endl;
}

int main(){
   // freopen("in.txt", "r", stdin);
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> T;
    while(T--) solve();
    return 0;
}